White's Studio.

LintCode-440. Backpack IIIFollow

LintCode
2018/08/24 Share

LintCode-440. Backpack IIIFollow

Description

Given n kind of items with size Ai and value Vi( each item has an infinite number available) and a backpack with size m. What’s the maximum value can you put into the backpack?

You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.

Have you met this question in a real interview? Yes

Problem Correction

Example

Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 15.

Analyst

  1. 最后一步

    F[n][m]表示前n个背包放入了重量m 的 value

    最后一个背包A[n-1]能被放入：

    F[n][m] = F[n-1][m-A[n-1]] + B[n-1]

    最后一个背包A[n-1] 不能被放入：F[n][m] = F[n-1][m]

  2. 顺序：由小到大

  3. 边界情况：

    前0个放入任意重量 F[0][m] = Integer.MIN_VALUE

  4. 状态方程：

    F[n][m] = Math.max(F[n-1][m] ,F[n-1][m-A[n-1]] + B[n-1])

Solution

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    /**
     * @param A: an integer array
     * @param V: an integer array
     * @param m: An integer
     * @return: an array
     */
    public int backPackIII(int[] A, int[] V, int m) {
        // write your code here
        int len = A.length;
        if (len == 0) 
            return 0;

        int [][] F = new int[m+1][m+1];

        for (int i = 0; i <= m; i ++) {
            F[0][i] = 0;
        }

        for (int i = 1; i <=m; i++) {
            for(int j = 0; j <= m; j ++) {
                F[i][j] = F[i-1][j];
                for (int k = 0; k <len; k++) {
                    if (j >= A[k]) F[i][j] = Math.max(F[i-1][j-A[k]] + V[k], F[i][j]);
                }
            }
        }

        int res = Integer.MIN_VALUE;
        for (int i = 0; i<=m ; i++) {
            res = Math.max(res, F[i][m]);
        }
    	return res;
	}
}

时间太长，会过不了测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int backPackIII(int[] A, int[] V, int m) {
        int[] F = new int[m+1];
        
        for (int j =0; j<=m ; j++) {
            F[j] = 0;
            if (j == 0) continue;
            
            for (int k = 0; k < A.length; k++) {
                if (j >= A[k]) F[j] = Math.max(F[j], F[j-A[k]] + V[k]);
            }
        }
        
        int max = 0;
        for (int i = 0; i <=m;  i++) {
            max = Math.max(max, F[i]);
        }
        return max;
    }

原文作者: White

原文链接: http://yuchenzhen.github.io/2018/08/24/LintCode-440. Backpack IIIFollow/

发表日期: August 24th 2018, 1:22:18

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. LintCode-440. Backpack IIIFollow
    1. 1.1. Description
    2. 1.2. Example
    3. 1.3. Analyst
    4. 1.4. Solution
Total : 31
2019
2018
Java Binary_Tree Python Node.js RPC git List Leetcode Leedcode LeetCode LintCode Node.js dubbo electron Java Spring-boot hexo 脑洞题 消息队列 Leetcode Java 数据结构，二叉树 Algorithm